package day32;

// 超时！

// 斐波那契凤尾

import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
/*            // 首先计算斐波那契数列
            int[] fib = new int[100001];
            fib[0] = 1;
            fib[1] = 1;
            for (int i = 2; i < fib.length; i++) {
                fib[i] = fib[i-2] + fib[i-1];
                // 注意存储的只是后六位就行,因为是相加 只保留后六位是不会影响后期的
                fib[i] = fib[i] % 1000000;
            }
            System.out.println(fib[n]);*/

            int first = 0;
            int second = 1;
            int third = 1;
            for (int i = 1; i <= n; i++) {
                third = (first +second) % 1000000;
                first = second;
                second = third;
            }
            System.out.println(third);
        }
    }
}
